#include <iostream>
#include <vector>
using namespace std;
// 70. 爬楼梯
// 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
//每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
// https://leetcode.cn/problems/climbing-stairs/description/

// 动态规划
class Solution {
public:
    int climbStairs(int n) {
        vector<int> memo(n+1, -1);

        memo[0] = 1;
        memo[1] = 1;
        for(int i = 2; i <= n; i++)
            memo[i] = memo[i-1] + memo[i-2];
        return memo[n];
    }
};
int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
